#ifndef SKIPLIST_H_
#define SKIPLIST_H_
#include<atomic>

template<typename K, typename V>
class SkipList {
private:
    struct Node;
public:
    SkipList();
    SkipList(const SkipList&) = delete;
    SkipList& operator=(const SkipList&) = delete;;
    void Insert(const K, const V);
    bool Contains(const K&);
    bool Erase(const K&);
    bool Update(const K&, const V& v);
    void Show();
    void DumpFile();
    void LoadFile();
    void SplitKV(const std::string&, std::string*, std::string*);
    int RandomHeight();

public:
    class Iterator {
    public:
        Iterator(const SkipList*);
        ~Iterator();
        bool Valid() const;
        const K& Key() const;
        const V& Value() const;
        void Next();
        void Prev();
        //void Seek(const K&);
        void SeekToFirst();
        void SeekToLast();

    private:
        const SkipList* list_;
        Node* node_;
    };
private:
    enum { kMaxHeight = 12 };
    int GetMaxHeight() const ;
    Node* NewNode(const K, const V, int);
    Node* FindGreaterOrEqual(const K&, Node**) const;
    Node* const head_;
    std::atomic<int> max_height_;

    Node* FindLast() const;
    Node* FindLessThan(const K&) const;
};
#endif 
